#include "../tools.h"
/**
 * 序列 nums 不包含重复数字，返回全排列
 * 
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 
 */

class Solution {
public:
    void backtrack(vector<vector<int>> &res, vector<int> &nums, int left_first){
        if (left_first == nums.size()){
            res.push_back(nums);
            return;
        }

        for(int i = left_first; i < nums.size(); ++i){
            swap(nums[left_first], nums[i]);
            backtrack(res, nums, left_first + 1);
            swap(nums[left_first], nums[i]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.size() == 0) return res;

        backtrack(res, nums, 0);
        return res;
    }
};


int main(int argc, char const *argv[])
{
    vector<int> nums = {1,2,3};

    Solution s;
    vector<vector<int>> res = s.permute(nums);

    show(res);
    
    return 0;
}
